package com.lsp.java.dataStructure.array;

import java.util.Arrays;

public class ArrayUtils {

    int[] elements;

    public ArrayUtils() {
        this.elements = new int[0];
    }

    public int size() {
        return elements.length;
    }

    //添加元素
    public void add(int args) {
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            //把老数组复制到新的数组内
            newArr[i] = elements[i];
        }
        newArr[elements.length] = args;
        elements = newArr;
    }

    //显示所有元素
    public void show() {
        System.out.println(Arrays.toString(elements));
    }

    //删除元素
    public void delete(int index) {
        if (index < 0 || index > elements.length - 1) {
            throw new RuntimeException("下标越界");
        }
        int[] newArr = new int[elements.length - 1];
        for (int i = 0; i < elements.length - 1; i++) {
            if (i < index) {
                newArr[i] = elements[i];
            } else {
                newArr[i] = elements[i + 1];
            }
        }
        elements = newArr;
    }

    //插入指定位置
    public void addIndex(int index, int arg) {
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            if (i < index) {
                newArr[i] = elements[i];
            } else {
                newArr[i + 1] = elements[i];
            }
        }
        newArr[index] = arg;
        elements = newArr;
    }

    //替换指定位置元素
    public void relace(int index, int element) {
        elements[index] = element;
    }

    //线性查找
    public int search(int target) {
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] == target) {
                return i;
            }
        }
        return -1;
    }

    //二分法查找元素,前提条件是数组是有序的
    public int binarySearch(int target) {
        //记录开始位置
        int begin = 0;
        //记录结束位置
        int end = elements.length - 1;
        //记录中间位置
        int mid = (begin + end) / 2;
        //记录查找的位置
        while (true) {
            if (begin >= end) {
                return -1;
            }
            //判断中间的这个元素是不是要查找的元素
            if (elements[mid] == target) {
                return mid;
                //中间这个元素不是要查找的元素
            } else {
                //判断中间这个元素是不是比要查找的元素大
                if (elements[mid] > target) {
                    //把结束位置调整到中间位置的前一个位置
                    end = mid - 1;
                    //判断中间这个元素是不是比要查找的元素小
                } else {
                    //把开始位置调整到中间位置的后一个位置
                    begin = mid + 1;
                }
                //取出新的中间位置
                mid = (begin + end) / 2;
//                if (mid == end || mid ==begin) {
//                    return -1;
//                }
            }
        }
    }

}
